package LearnAlgorithm.h_标准数学公式;


public class i判断素数by埃式筛法 {
	public static void main(String[] args) {
		long currentTimeMillis = System.currentTimeMillis();
		primeFindAiShi(100000);//第10万个素数，在从0开始的自然数中的数值是1299709
		System.out.println((System.currentTimeMillis() - currentTimeMillis) + "ms");
	}
	
	/**
	 * 根据素数定理
	 * 自然数n内，素数的个数约等于ln(n)
	 * N*log(N)*log(N)

N是第N个素数
已知在整数X内大概有 X / lg(X) 个素数
现在我们要逆推：
要想求第N个素数，我们的整数范围是什么
lengthX就是整数范围

	 * @param N
	 */
	public static void primeFindAiShi(int N) {
		int lengthX = 2;
		while (lengthX / Math.log(lengthX) < N) {//Math.log以10为底
			lengthX++;
		}
		int[] arr = new int[lengthX];//开辟一个数组，下标是自然数， 元素值是标记
		int x = 2;
		while (x < lengthX) {//基本思路是筛选法，把非素数标记出来
			if (arr[x] != 0) {//判断标记过了，那就跳过，判断下一个x
				x++;
				continue;
			}
			int k = 2;//对每个x，我们从2倍开始，对x的k倍， 全部标记为-1
			while (x * k < lengthX) {
				arr[x * k++] = -1;
			}
			x++;
		}
		int sum = 0;//筛完之后，这个很长的数组里面非素数下标对应的值都是-1
		for (int i = 2; i < arr.length; i++) {
			if (arr[i] == 0) {
				sum++;
			}
			if (sum == N) {
				System.out.println(i);
				return;
			}
		}
	}
}
